\input{regression-test.tex}
\documentclass[degree=doctor]{thuthesis}

\begin{document}
\START
\showoutput

\mainmatter

\setcounter{chapter}{2}
\chapter{对等网络中宽松约束的一般性搜索的理论模型}

\section{本章引论}

本章为 P2P 中宽松约束的一般性搜索建立理论模型，以研究此类搜索的效率和带宽开销。
根据本章的理论模型可以很好地测算出各种条件下及不同应用中的 P2P 搜索效率和带宽开销，为 P2P 中宽松约束搜索的研究建立了基础。
通过模型求解可以得到搜索所需的瓶颈资源（即结点带宽）的理论下限，并可算出不同系统参数下最优的搜索性能以及达到此性能时的最优数据索引分布，从而为 P2P 系统搜索算法的设计、性能优化、性能比较以及可行性分析提供了一般性方法。
后面第四章提出的近似最优的实用搜索算法就是直接应用本章模型和结论而设计的。\footnote{%
  脚注处序号“①，……，⑩”的字体是“正文”，不是“上标”，序号与脚注内容文字之间空半个汉字符，脚注的段落格式为：单倍行距，段前空 0 磅，段后空 0 磅，悬挂缩进 1.5 字符；字号为小五号字，汉字用宋体，外文用 Times New Roman 体。
}

从第 2 章讨论可知，宽松约束搜索的用途非常广泛，是广域网上多服务器系统的基础功能和服务。
为了明确起见，这里重述一下定义：所谓“宽松约束”是指搜索不要求返回全部符合条件的结果，而只要返回一个或若干个（根据用户要求而定）即可；所谓“一般性搜索”是指搜索算法必须是普适的，具体来说就是搜索条件任意和数据存放位置任意。
目前尚不能很好地解决此类搜索问题，主要面临的问题是算法网络通信量过大，很容易超过结点和网络的承受能力，造成严重的带宽开销和系统不可扩展（non-scalable）的问题。
现有算法中，结构化 P2P 中精确匹配数据标识的数据定位算法无法支持各种非精确匹配的搜索（如子串匹配的搜索）。
Gnutella 等非结构化 P2P 系统依靠消息转发的随机搜索方法虽然符合一般性搜索的要求，但是存在严重的性能问题。
由于 P2P 巨大的结点数和数据量，不加优化的随机搜索面临“大海捞针”的困境，搜索消息通常要游历很多无关结点并产生大量冗余消息之后才能找到数据。
因此，不论使用消息洪泛[2]或是性能稍好的随机走步[45]，普遍认为 Gnutella 式的随机搜索算法不具可扩展性[47]，当结点较多时带宽约束将造成非常严重的系统瓶颈。带宽约束正是制约此类 P2P 搜索的最大问题。

为了解决通信量过大的问题，人们尝试了很多优化措施来改进基础设施和搜索算法的各个方面，包括使用冗余更少和通信方面更“温和”的消息转发算法、采用混合结构、使用超级结点的偏向性搜索、扩散数据索引和缓存搜索结果等等[42-54,106]。
其中最为重要的手段就是主动扩散数据索引，即结点不只存储自身数据，同时缓存其他结点所存数据的索引（参见 2.3.1 节）。
由于数据的分布是任意的，搜索不可避免地带有盲目性，平均搜索跳数总是依赖于“知道”目标数据的结点个数而难于进一步提高（详见 3.2 节的分析）。
因此在一般性搜索问题中，通过扩散索引来增加数据知名度的方法成为本质上的解决途径。

然而索引扩散并不总是有效率的，它也会带来带宽开销。一方面，扩散更多的索引可以使搜索更快地返回，减少了搜索带宽开销；另一方面，由于 P2P 中结点和数据处于不断动态变化之中，当数据失效或更新时（如结点离线、删除或更新数据），数据的索引也相应失效，必须加以更新维护。
因此，扩散更多的索引意味着维护开销的增加。于是在带宽开销方面，搜索开销与索引维护开销之间存在着折衷关系（trade-off）。
与以往工作中仅考虑搜索开销不同，本章的模型中我们同时考虑搜索和维护两方面，给出了索引扩散方法对搜索整体性能的影响和数学关系。
通过模型我们发现索引数量是决定宽松约束一般性搜索性能的至关重要的因素，采用最优索引分布可以很大程度上提高性能，降低系统开销。
与一般认为的 P2P 无偏向性搜索难于扩展（non-scalable）恰恰相反，模型显示在最优的索引扩散策略下，基于无偏向性搜索具备很好的可扩展性，其结点负载和带宽开销随系统规模 $N$（结点数）增长具有 $O(\sqrt{N})$ 的增长关系。这种平方根关系保证了对大规模 P2P 系统很好的适应性。

本章剩余部分按照如下方式组织：
3.2 节给出模型假设；
3.3 节推导出带宽开销和搜索效率的计算公式，给出性能模型；
3.4 节通过优化索引分布得到了理论最优的宽松约束搜索，证明了对可扩展性具有重要意义的“平方根关系”；
3.5 节对模型结论和意义进行了总结；
3.6 节讨论模型适应性并和相关工作进行了比较，最后是本章小结。


\section{模型基本假设}

一般性搜索要解决任意可能的数据存放方式和任意的查询条件下的搜索问题。
任意可能的数据存放意味着数据与存放结点之间可以不存在任何相关性，因而无法利用类似兴趣偏好、结点特性或数据存放的规则来指导消息转发或优化性能，单步搜索效率等同于盲目搜索（blind search）。
任意的查询条件，意味着只有获得了完整的元数据（数据中用来被查询的部分）才可以判断出该数据是否符合查询条件，单靠部分元数据不能解决所有可能的查询请求。
这样以往针对特定搜索条件的倒排式索引（如关键词倒排表等）无法发挥作用，只能使用正排式的数据索引。
这样，一般性搜索限制了可能采取的优化措施，使搜索性能存在理论极限。

虽然在特定应用中使用的不一定是严格的“一般性搜索”，其数据与结点之间可能存在一定的相关性，并且可以借助搜索条件的特性来优化性能，但是本章只讨论最一般的情况，目的在于建立基础性的模型，研究和寻找适用于绝大多数应用的宽松约束搜索算法。
针对特定搜索条件的高效搜索算法可参见第五章，利用数据和结点的语义相关性来优化性能的研究参见第六章。

本节针对 P2P 中一般性搜索的特点给出模型的基本假设，具体包括搜索的“无偏向性”、结点特性以及系统的短时稳态假设。
我们首先讨论这三方面问题，最后给出模型假设的总体叙述。


\subsection{无偏向性搜索}

如果 P2P 中所有结点都以相同或相近的概率接收到搜索请求，那么称此搜索算法为“无偏向性搜索（unbiased search）”。
无偏向搜索可看作是对等网络搜索的基础，也是应用最多的一种。
这是由于对等网络中单结点能力较弱，只有让所有结点均摊巨大的总体搜索负载，才可能支撑起高强度的搜索算法。
如果搜索消息不能近似均匀地散落在所有结点上，那么负载重的结点很容易发生过载。
均衡负载的思想正是对等网络存在和发展的基础，即集合众多微小的力量（大量弱结点）形成巨大的总体服务能力。
实际应用中，只要搜索算法在选择邻居结点转发消息时没有特殊的偏向性，那么就可以近似认为是无偏向性搜索，譬如最常用的洪泛和随机走步就是无偏向性算法。
模型中我们假设搜索算法是无偏向性的。
对于使用了超级结点的偏向性搜索，通常可认为是将结点划分为不同类别。
同一类别的结点运行相同的算法和协议，因此各类别内部仍然是无偏向性搜索，符合模型假设。
此时可针对每个类别的结点群体分别使用模型，从而得出整体算法的性能（详见 3.5 节）。

由于数据分布是随机的，且结点收到搜索消息的概率彼此相同，因此无偏向性条件下单步搜索的成功概率不会优于盲目搜索的性能。
虽然搜索途中遇到的结点可带来历史信息并指导后续遍历，但由于巨大的结点数和数据量以及数据随机存放的特点，小量历史信息的作用非常有限，且与特定应用的性质相关。
因此模型中对此不作考虑，仍然以盲目搜索作为无偏向性搜索单步性能。


\subsection{结点特性}

P2P 中结点总处于不断地动态变化之中，随时有结点加入和离开系统。
动态性显著地影响系统性能和索引的有效性。
按照 P2P 中通常的假设，结点的行为（在线或离线）独立于其他结点，并且所有结点具有统一的动态特性以及在线时间分布，这种分布一般用指数分布来刻画。
具体来说，设结点的平均在线服务时间（session time）为 $T_{\text{session}}$，则单个结点在线时间长度符合参数 $\lambda = 1/T_{\text{session}}$ 的指数分布。
由于结点动态变化彼此独立，因此一段时间之内发生的动态变化次数符合泊松分布，其参数与指数分布参数一致。


\subsection{短时稳态性}

我们假设 P2P 系统具有短时稳态特性，即一段不长的时间中系统的性质（如结点平均在线时间 $T_{\text{session}}$、数据总量、数据访问频度分布）以及系统规模（结点数 $N$）不会发生显著的变化。
尽管长时程中系统性质可能会明显变化，但是这种变化总是靠缓慢的积累而产生的。
因此，可以用一个稳态模型来描述 P2P 系统，而 P2P 系统的长程变化可以用同一个稳态模型的不同参数取值点来刻画。


\subsection{模型假设的总体叙述}

综合以上三方面就得到本章理论模型的基本假设。
具体而言，模型假设 P2P 系统和一般性搜索算法具有如下特点：一般性搜索算法对结点不具有偏向性，所有结点以相同或相近的概率收到搜索请求；结点在线时间可用独立同分布的指数分布来描述；P2P 系统在相对较短的时间段内可看作是稳态，系统主要参数保持不变。
以上假设是针对 P2P 系统及一般性搜索的特点而做出的，具有广泛的适应性，可用来研究目前大多数 P2P 宽松约束搜索系统的性能。
关于模型适应性将在 3.6.1 节做进一步讨论。


\section{宽松约束的一般性搜索性能理论模型}

本节建立无偏向性搜索的理论模型，模型统一解决无偏向性搜索的带宽开销计算、带宽开销的理论下限、最优的搜索性能以及最优索引分布。
模型中用到的符号及说明参见表~\ref{tab:notations}。

\newcommand\BWsearch{\mathit{BW}_{\text{search}}}
\newcommand\BWmaintain{\mathit{BW}_{\text{maintain}}}
\newcommand\BWtotal{\mathit{BW}_{\text{total}}}
\newcommand\bwpeer{\mathit{bw}_{\text{peer}}}

\begin{table}[htb]
  \centering
  \caption{无偏向搜索模型的符号表}
  \label{tab:notations}
  \begin{tabular}{cp{0.7\textwidth}}
    \toprule
    符号                                & 意义及说明                                                                                       \\
    \midrule
    $N$                                 & 结点总数。代表了系统规模                                                                         \\
    $M$                                 & 彼此不同的数据的个数。注意数据副本不计入 $M$ 中                                                  \\
    $f_1, f_2, \dots, f_M$              & 系统中 $M$ 个彼此不同的数据                                                                      \\
    $q_1, q_2, \dots, q_M$              & 数据的访问频度分布向量                                                                           \\
    $C_i$                               & 数据 $f_i$ 的索引个数。亦即 $f_i$ 的应答结点的个数                                               \\
    $\mathit{INV}_i$                    & 数据 $f_i$ 的索引失效率。每 1 秒内失效的 $f_i$ 索引占全部 $f_i$ 索引的比例                       \\
    $\mathit{INV}$                      & 当数据具有相近的更新频度时，索引失效率用统一的 $\mathit{INV}$ 表示                               \\
    $\mathit{INV}_{\text{max}}$         & $\max\{ \mathit{INV}_i \mid i = 1, 2, \dots, M \}$，即所有失效率的最大值。
                                          如果不考虑数据之间更新频度的差异，则 $\mathit{INV}_{\text{max}} = \mathit{INV}_i = \mathit{INV}$ \\
    $R_{\text{search}}$, $L_{\text{S}}$ & 搜索消息冗余数和搜索消息的比特数。刻画搜索的消息转发开销                                         \\
    $R_{\text{update}}$, $L_{\text{U}}$ & 维护消息冗余数和维护消息的比特数。刻画维护索引的消息开销                                         \\
    $\BWsearch$, $\BWmaintain$          & 系统中搜索使用的总带宽开销和维护使用的总带宽开销                                                 \\
    $\BWtotal$, $\bwpeer$               & 系统总带宽开销与单个结点上的带宽开销。是搜索与维护开销之和                                       \\
    $C_i^*$                             & 使带宽开销最小化的索引数量（指数据 $f_i$ 的索引）                                                \\
    $\bwpeer^*$                         & 结点的理论带宽下限。当所有 $f_i$ 的索引数都等于对应的 $C_i^*$ 时取到                             \\
    $\mathit{BA}$                       & 结点的可用带宽约束。$\mathit{BA}$ 必须不小于 $\bwpeer^*$                                         \\
    $\mathit{Hops}$                     & 单次搜索所需遍历的不同结点数的期望。刻画搜索等待时间                                             \\
    $\xi$                               & 索引的放大系数，即约束下的最优索引数 $C_i$ 与最小化带宽的索引数 $C_i^*$ 的比值。
                                          $\xi$ 由带宽约束 $\mathit{BA}$ 与带宽下限 $\bwpeer^*$ 的比值决定                                 \\
    $\theta$                            & 与 $N$ 无关的系统常量，刻画了搜索与维护之间的折衷关系。用 $\theta$ 可简化索引比例 $k_i$ 的表示   \\
    \bottomrule
  \end{tabular}
\end{table}


\subsection{单次搜索的带宽开销以及系统总带宽开销}

无偏向性搜索中，单次搜索的带宽开销与索引数量之间存在如下基本关系。
考虑对等网络中有 $N$ 个结点，其中有 $C_f$ 个结点存放了数据 $f$ 的索引（存储数据 $f$ 本身的那些结点也被认为包含 $f$ 的索引）。
称这些结点为 $f$ 的“应答结点”，只有它们能够应答以 $f$ 为目标的搜索。
考虑某个需要 $f$ 的结点发起一次搜索请求，显然当且仅当该请求的消息被转发到 $f$ 的应答结点上，该请求才能够得以回应。
因此，每当搜索消息被发送到一个尚未遍历过的新结点，如果该结点上具有 $f$ 的索引，则搜索过程结束，成功返回；否则搜索继续，寻求尚未遍历的新结点。
于是搜索成为一个随机过程，可用贝努利实验来刻画。
由于总共有 $N$ 个结点，其中有 $C_f$ 个应答结点，所以无偏向性搜索中新遍历的结点可使搜索结束的概率是 $C_f / N$。
由贝努利实验可知，搜索到 $f$ 需要遍历的结点个数的期望满足：
\begin{equation}
  E \{\text{搜索 $f$ 所遍历的不同结点的个数}\} = \left(\frac{C_f}{N}\right)^{-1} = \frac{N}{C_f}
\end{equation}

为了计算搜索过程占用的网络带宽，定义“搜索消息冗余数”$R_{\text{search}}$，表示平均每个结点在一次搜索请求中收到的重复的搜索消息数。
显然在一次搜索中，同一个结点收到多次转发来搜索消息是没有意义的，只会带来带宽的浪费。
但是现实搜索算法并非都是无冗余的，譬如洪泛算法使用并发的消息广播，搜索消息会沿着不同路径多次抵达同一结点，因此其 $R_{\text{search}}$ 值就相当大。
随机走步算法通过记录遍历结点的办法实现无冗余的消息转发，可以认为 $R_{\text{search}} = 1$。

从上述分析可以看出，索引分布数量对搜索效率和带宽消耗有很大影响。
数据索引分布越广（即 $C_f$ 越大），该数据就越容易被搜索，使用的搜索带宽也就越小。
另一方面索引会因为所指向的实际数据的变动而失效，需要持续不断地维护，否则就有效的数据索引个数就会不断减少，直至为零。
因此系统总带宽开销 $\BWtotal$ 由搜索带宽开销 $\BWsearch$ 和索引的维护带宽开销 $\BWmaintain$ 两部分组成的，即：
\begin{equation}
  \BWtotal = \BWsearch + \BWmaintain
\end{equation}

下面分别计算 $\BWsearch$ 和 $\BWmaintain$，从而得到性能模型。


\subsection{索引分布与搜索开销的关系}

首先计算搜索的带宽开销。
考虑 P2P 系统有 $N$ 个结点，共享了 $M$ 个彼此不同的数据 $f_1, f_2, \dots, f_M$。
注意同一个数据 $f$ 可以有多个副本（replicas）存储在不同结点上。
这种情况在 P2P 中很常见，譬如 P2P 文件共享应用中的多个文件副本，以及多服务器联合服务时由不同服务器提供的相同服务。
这里副本不计入 $M$ 中。

考察数据索引分布情况，设数据 $f_i$ 有 $C_i$ 个索引。
为计算搜索带宽消耗，需要考察系统中搜索任务以及在各数据上的分配。
假设系统单位时间内总共产生 $Q$ 次搜索。
每一个数据根据自身情况，具有不同的访问频度（popularity）。
访问频度高的（即热门的）数据被搜索和使用的更多，因而在 $Q$ 中占据更多的份额。
我们用分布向量 $q = \langle q_1, q_2 , \dots, q_M \rangle$ 表示各数据的访问频度，其中 $q_i$ 为正数，表示对于一次系统中出现的搜索，数据 $f_i$ 满足搜索条件的概率，而全部 $q_i$ 的总合为 1。
这样根据 3.2.2 小节可得到搜索带宽开销 $\BWsearch$ 为：
\begin{equation}
  \BWsearch = \sum_{i=1}^M Q \cdot q_i \cdot \frac{N}{C_i} \cdot R_{\text{search}} \cdot L_{\text{S}}
\end{equation}




\chapter{对等网络中宽松约束的一般性搜索的理论模型}

如果章标题过长需要分行书写的话，则第一行段前空 24 磅，段后空 0 磅，回车后，第二行段前空 0 磅，段后空 24 磅。
见上面的样式例子。



\clearpage
\OMIT
\end{document}
